package org.chen.practice.middle;

/**
 * @Author chen
 * @Date 2023/7/20 23:50
 * 题目描述
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 *
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }

    /**
     * 动态规划
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int len = s.length();
        if(len<2){
            return s;
        }
        int maxlen =1;
        int begin =0;
        // dp[i][j] 表示s[i..j]是否是回文串
        // 状态转移方程：dp[i][j] = s[i] == s[j] dp[i+1][j-1]
        boolean[][] dp = new boolean[len][len];
        // 初始化长度为1的子串都是回文
        for(int i=0;i<len;i++){
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        // 递推开始
        // 枚举字串长度，左下角先填写
        for(int L = 2;L<=len;L++){
            // 枚举左边界
            for(int i=0;i<len;i++){
                // 由L和i可以确定右边界，即j-i+1=L
                int j= L+i-1;
                // 如果右边界越界，就退出当前循环
                if(j>=len){
                    break;
                }
                if(charArray[i] != charArray[j]){
                    dp[i][j]=false;
                }else{
                    // 边界条件: j-1-(i+1)+1<2,整理j-i<3 <=> j-i+1=4
                    if(j-i<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 只要dp[i][L] == true 成立，就表示字串s[i..L]是回文，记录回文长度和起始地址位置
                if(dp[i][j]&&j-i+1>maxlen){
                    maxlen=j-i+1;
                    begin=i;
                }

            }
        }
        return s.substring(begin,begin+maxlen);
    }

    /**
     * 中心扩散法
     * 时间复杂度O(n^2) 空间复杂度O(1)
     * @param s
     * @return
     */
    public static String longestPalindromeByCenterExpand(String s) {
        return null;
    }

    /**
     * Manacher算法
     * 时间复杂度O(n) 空间复杂度O(1)
     * @param s
     * @return
     */
    public static String longestPalindromeByManacher(String s) {
        return null;
    }



}
